(* 完全二叉树: 除了最后一层外，其他每一层的节点数都达到最大,
最后一层的节点从左到右连续排列，中间不能有空缺 *)

type 'a binary_tree =
  | Empty
  | Node of 'a * 'a binary_tree * 'a binary_tree   (* 当前节点 ，当前左子树，当前右子树 *)
;;

let rec split_n lst acc n = match (n, lst) with
    | (0, _) -> (List.rev acc, lst)
    | (_, []) -> (List.rev acc, [])
    | (_, h :: t) -> split_n t (h :: acc) (n-1)

(* 情况1：子节点列表为空
| (p, []) -> 将父节点列表中的每个元素x转换为叶子节点Node(x, Empty, Empty)
情况2：父节点非空且子节点只剩1个
| (x :: t, [y]) -> 创建当前节点：左子树为y，右子树为空 Node (x, y, Empty) 
递归处理剩余父节点t和空子节点列表 :: myflatten t []
情况3：父节点非空且子节点有至少2个
| (ph :: pt, x :: y :: t) -> 创建当前节点：左子树为x，右子树为y (Node (ph, x, y)) 
递归处理剩余父节点pt和剩余子节点t :: myflatten pt t *)
  let rec myflatten p c = 
    match (p, c) with
    | (p, []) -> List.map (fun x -> Node (x, Empty, Empty)) p
    | (x :: t, [y]) -> Node (x, y, Empty) :: myflatten t []
    | (ph :: pt, x :: y :: t) -> (Node (ph, x, y)) :: myflatten pt t
    | _ -> invalid_arg "myflatten"

(* 定义一个内部递归函数 aux l lst，其中 l 表示当前树的层数（从0开始），lst 是剩余待处理的列表。
对于每一层 l，使用 split_n lst [] (1 lsl l) 将列表 lst 分割为两部分：
p：当前层的父节点列表。c：剩余的子节点列表。
1 lsl l 表示将数字1左移 l 位，相当于计算 2^l。这用于确定当前层需要多少个父节点。
使用 myflatten p c 将父节点列表 p 和子节点列表 c 转换为当前层的节点列表。
myflatten 函数将父节点列表 p 和子节点列表 c 配对，每个父节点对应两个子节点（如果存在），生成一个节点列表。
递归调用 aux (l + 1) 处理下一层，即 l + 1 层。
最终，List.hd (aux 0 lst) 返回整个树的根节点。 *)

let complete_binary_tree = function
  | [] -> Empty
  | lst ->
      let rec aux l = function
        | [] -> []
        | lst -> let p, c = split_n lst [] (1 lsl l) in 
                myflatten p (aux (l + 1) c)
      in
        List.hd (aux 0 lst);;

complete_binary_tree [1; 2; 3; 4; 5; 6];;